Aufgabe 3.2.2:

Die Übergangstabelle eines DEA siehe wie folgt aus:

\begin{matrix}| & 0 & 1 \\ → q_{1} & q_{2} & q_{3} \\ q_{2} & q_{1} & q_{3} \\ ^{∗}q_{3} & q_{2} & q_{1} \end{matrix}

Die Graph eines DEA sehe wie folgt aus:

q_{1}  q_{2}  q_{3} 0 0  1 0 1 1

a) Formulieren Sie alle regulären Ausdrücke R_{ij}^{(0)}. Hinweis: Stellen Sie sich den Zustand q_{i} so vor, als handle es sich um den Zustand mit der ganzzahligen Nummer i.

b) Formulieren Sie alle regulären Ausdrücke R_{ij}^{(1)}. Versuchen Sie die Ausdrücke so weit wie möglich zu vereinfachen.

c) Formulieren Sie alle regulären Ausdrücke R_{ij}^{(2)}. Versuchen Sie die Ausdrücke so weit wie möglich zu vereinfachen.

d) Formulieren Sie einen regulären Ausdruck für die Sprache des Automaten.

e) Konstruieren Sie das Übergangsdiagramm für den DEA, und geben sie einen regulären Ausdruck für die Sprache des Automaten an, indem sie q_{2} eleminieren.

Lösung:

a) Analog zu Aufgabe 3.2.1 werden nun alle R_{ij}^{(0)} für alle i, j ∈ {1, 2, 3} bestimmt. Zur Verkürzung wird hier auf längere Erklärungen verzichtet:

1) R_{11}^{(0)} = ε

2) R_{12}^{(0)} = 0

3) R_{13}^{(0)} = 1

4) R_{21}^{(0)} = 0

5) R_{22}^{(0)} = ε

6) R_{23}^{(0)} = 1

7) R_{31}^{(0)} = 1 8) R_{32}^{(0)} = 0

9) R_{33}^{(0)} = ε

b) Analog zu Aufgabe 3.2.1 werden nun aus den R_{ij}^{(0)} alle R_{ij}^{(1)} gebildet mit R_{ij}^{(k)} = R_{ij}^{(k−1)} + R_{ik}^{(k−1)}(R_{kk}^{(k−1)})^{∗}R_{kj}^{(k−1)}:

1) R_{11}^{(1)}= R_{11}^{(1−1)} + R_{11}^{(1−1)}(R_{11}^{(1−1)})^{∗}R_{11}^{(1−1)}

= ε + ε(ε)^{∗}ε = ε

2) R_{12}^{(1)}= R_{12}^{(1−1)} + R_{11}^{(1−1)}(R_{11}^{(1−1)})^{∗}R_{12}^{(1−1)}

= 0 + ε(ε)^{∗}0 = 0

3) R_{13}^{(1)}= R_{13}^{(1−1)} + R_{11}^{(1−1)}(R_{11}^{(1−1)})^{∗}R_{13}^{(1−1)}

= 1 + ε(ε)^{∗}1 = 1

4) R_{21}^{(1)}= R_{21}^{(1−1)} + R_{21}^{(1−1)}(R_{11}^{(1−1)})^{∗}R_{11}^{(1−1)}

= 0 + 0(ε)^{∗}ε = 0

5) R_{22}^{(1)}= R_{22}^{(1−1)} + R_{21}^{(1−1)}(R_{11}^{(1−1)})^{∗}R_{12}^{(1−1)}

= ε + 0ε^{∗}0 = ε + 00

6) R_{23}^{(1)}= R_{23}^{(1−1)} + R_{21}^{(1−1)}(R_{11}^{(1−1)})^{∗}R_{13}^{(1−1)}

= 1 + 01

7) R_{31}^{(1)}= R_{31}^{(1−1)} + R_{31}^{(1−1)}(R_{11}^{(1−1)})^{∗}R_{11}^{(1−1)}

= 1 + 1ε^{∗}ε = 1

8) R_{32}^{(1)}= R_{32}^{(1−1)} + R_{31}^{(1−1)}(R_{11}^{(1−1)})^{∗}R_{12}^{(1−1)}

= 0 + 01

9) R_{33}^{(1)}= R_{33}^{(1−1)} + R_{31}^{(1−1)}(R_{11}^{(1−1)})^{∗}R_{13}^{(1−1)}

= ε + 11

c) Analog zu Aufgabe 3.2.1 werden nun aus den R_{ij}^{(1)} alle R_{ij}^{(2)} gebildet mit R_{ij}^{(k)} = R_{ij}^{(k−1)} + R_{ik}^{(k−1)}(R_{kk}^{(k−1)})^{∗}R_{kj}^{(k−1)}:

1) R_{11}^{(2)}= R_{11}^{(2−1)} + R_{12}^{(2−1)}(R_{22}^{(2−1)})^{∗}R_{21}^{(2−1)}

ε + 0(ε + 00)^{∗}0 ε + 0(00)^{∗}0

2) R_{12}^{(2)}= R_{12}^{(2−1)} + R_{12}^{(2−1)}(R_{22}^{(2−1)})^{∗}R_{22}^{(2−1)}

= 0 + 0(ε + 00)^{∗}(ε + 00) = 0 + 0(00)^{∗}

3) R_{13}^{(2)}= R_{13}^{(2−1)} + R_{12}^{(2−1)}(R_{22}^{(2−1)})^{∗}R_{23}^{(2−1)}

= 1 + 0(00)^{∗}(1 + 01) = 1 + 0(00)^{∗}1 + 0(00)^{∗}01

4) R_{21}^{(2)}= R_{21}^{(2−1)} + R_{22}^{(2−1)}(R_{22}^{(2−1)})^{∗}R_{21}^{(2−1)}

= 0 + (ε + 00)^{∗}0 = 0 + (00)^{∗}0 = 0(00)^{∗}

5) R_{22}^{(2)}= R_{22}^{(2−1)} + R_{22}^{(2−1)}(R_{22}^{(2−1)})^{∗}R_{22}^{(2−1)}

(ε + 00) + (ε + 00)(ε + 00)^{∗}(ε + 00) (ε + 00)^{∗}

6) R_{23}^{(2)}= R_{23}^{(2−1)} + R_{22}^{(2−1)}(R_{22}^{(2−1)})^{∗}R_{23}^{(2−1)}

= (1 + 01) + (ε + 00)(ε + 00)^{∗}(1 + 01) = (00)^{∗}(1 + 01) = (00)^{∗}1 + (00)^{∗}01

7) R_{31}^{(2)}= R_{31}^{(2−1)} + R_{32}^{(2−1)}(R_{22}^{(2−1)})^{∗}R_{21}^{(2−1)}

= 1 + (0 + 10)(00)^{∗}0 = 1 + 0(00)^{∗}0 + 10(00)^{∗}0

8) R_{32}^{(2)}= R_{32}^{(2−1)} + R_{32}^{(2−1)}(R_{22}^{(2−1)})^{∗}R_{22}^{(2−1)}

= 0 + 01 + (0 + 01)(ε + 00)^{∗}(ε + 00) = 0 + 01 + (0 + 01)(00)^{∗} = 0 + 01 + 0(00)^{∗} + 01(00)^{∗} = 0(00)^{∗} + 01(00)^{∗}

9) R_{33}^{(2)}= R_{33}^{(2−1)} + R_{32}^{(2−1)}(R_{22}^{(2−1)})^{∗}R_{23}^{(2−1)}

= ε + 11 + (0 + 10)(ε + 00)^{∗}(1 + 01) = ε + 11 + (0(00)^{∗} + 10(00)^{∗})(1 + 01) = ε + 11 + 0(00)^{∗}1 + 0(00)^{∗}01 + 10(00)^{∗}1 + 10(00)^{∗}01

d) Um den Ausdruck zu formulieren, der die selbe Sprache beschreibt, wie der DEA, müssen alle Teilausdrücke R_{ij}^{(3)} für alle i ∈ q_{0} und j ∈ F (alle Ausdrücke die vom Startzustand zu einem akzeptierenden Zustand führen) vereinigt werden. Das betrifft bei diesem DEA nur jenen Ausdruck, der von Zustand 1(q_{0}) zu Zustand 3 (q_{2}) führt. Genauer:

R_{DEA} = R_{13}^{(3)}

Also muss noch der Ausdruck R_{13}^{(3)} gebildet werden:

R_{13}^{(3)}= R_{13}^{(2)} + R_{13}^{(2)}(R_{33}^{(2)})^{∗}R_{33}^{(2)} = 1 + 0(00)^{∗}1 + 0(00)^{∗}01 + (ε + 11 + 0(00)^{∗}1 + 0(00)^{∗}01 + 10(00)^{∗}1 + 10(00)^{∗}01)^{∗} = 1 + 0(00)^{∗}1 + 0(00)^{∗}01 + (11 + 0(00)^{∗}1 + 0(00)^{∗}01 + 10(00)^{∗}1 + 10(00)^{∗}01)^{∗} = 1 + 0(00)^{∗}(1 + 01) + (11 + 0(00)^{∗}(1 + 01) + 10(00)^{∗}(1 + 01))^{∗} = 1 + 0(00)^{∗}(1 + 01) + (11 + (0(00)^{∗} + 10(00)^{∗})(1 + 01))^{∗}

e) Der Graph des DEA sieht wie folgt aus:

q_{1}  q_{2}  q_{3} 0 0  1 0 1 1

Auf den Übergangspfeilen des DEAs stehen im Moment noch Zeichenreihen. Diese werden als erstes in reguläre Ausdrücke umgeschrieben. Danach sieht der DEA mit regulären Ausdrücken auf den Pfeilen wie folgt ausreguläre Ausdrücke seien hier mal fett gedruckt:

q_{1}  q_{2}  q_{3} 0 0  1 0 1 1

Man beachte, dass der reguläre Ausdruck, der die Zeichenkette bestehend aus {a} beschreibt, a lautet. Deshalb hat sich am Graphen selbst nichts geändert. Um nun den Zustand q_{2} zu eliminieren werden wie im Buch beschrieben, die r. Audrücke die zum Zustand q_{2} führen (seien a), die vom Zustand q_{2} zu sich selbst führen (seien b) und die, die vom Zustand weg führen (seien c) aneinander gereiht, in der Form abc. Da es noch Pfade gibt, die genau in die andere Richtung verlaufen, muss das ganze auch von q_{3} nach q_{1} in der Gegenrichtung gemacht werden. Dies führt zu dem folgenden Übergangsgraphen:

q_{1}  q_{3} 1 +01 1 + 00

Aus diesem Graphen lässt sich leicht ein Ausdruck formulieren, der die selbe Sprache beschreibt, wie der DEA: Man muss mindestens einmal von q_{1} nach q_{3} kommen. Von da an kann man beliebig oft (auch 0 mal) zurück zu q_{1} und von dort aus wieder zu q_{3}. Das ergibt den folgenden Ausdruck:

(1 + 01)((1 + 00)(1 + 01))^{∗}  (1)